package com.lwl.Algorithmic_data_structure.class28Manacher马拉车;

/**
 * @author lwl
 * @Description 求最大回文子串，Code01_Manacher中是非常简化版
 * @date 2023/6/27 21:51
 */
public class Code01Manacher {

    public static void main(String[] args) {
        // 5
        System.out.println(manacher("baadaaecab"));
        // 3
        System.out.println(manacher("edaaeaeedadaeaad"));
        // 4
        System.out.println(manacher("ccccabbddbed"));
        // 7
        System.out.println(manacher("bbebabeeeba"));
    }

    public static int manacher(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = addCharToString(s);
        int res = 0;
        int right = -1;
        int center = -1;
        // 回文半径的大小
        int[] radiusArr = new int[str.length];
        /*
         * 在圈外就正常遍历
         *
         * 当前i在圈内有三种情况：（i`为i以圆心center对称的位置）
         * 1. i`圈住的地方在当前圈内：i的半径即为i`的半径
         * 2. i`圈住的地方超出当前圈，i的半径为right-i
         * 3. i`圈主的地方与当前圈相切，i的半径至少为right-i，需要探索圈外的字符串
         */
        for (int i = 0; i < str.length; i++) {
            // i`在圈外
            if (right <= i) {
                int radius = 1;
                while (i - radius >= 0 && i + radius < str.length && str[i - radius] == str[i + radius]) {
                    radius++;
                }
                right = i + (radius - 1);
                center = i;
                res = Math.max(res, radius - 1);
                radiusArr[i] = radius - 1;
                continue;
            }
            // i`在圈内
            // 1. i`圈住的地方在当前圈内：i的半径即为i`的半径
            // center - (i - center)
            if (i + radiusArr[2 * center - i] < right) {
                radiusArr[i] = radiusArr[center - (i - center)];
            } else if (i + radiusArr[2 * center - i] > right) {//2. i`圈住的地方超出当前圈，i的半径为right-i
                radiusArr[i] = right - i;
            } else {//3. i`圈主的地方与当前圈相切，i的半径至少为right-i，需要探索圈外的字符串
                int radius = right - i;
                while (i - radius >= 0 && i + radius < str.length && str[i - radius] == str[i + radius]) {
                    radius++;
                }
                right = i + (radius - 1);
                center = i;
                res = Math.max(res, radius - 1);
                radiusArr[i] = radius - 1;
            }
        }
        return res;
    }

    private static char[] addCharToString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }
}
